package com.algrithom.array;

import java.util.Arrays;
import java.util.Locale;

/**
 * 数组相关算法 1：快慢指针 2：滑动窗口
 *
 * @author think
 * @version 1.0.0
 * @since 2020/1/1
 */
public class Solution1 {
    
    public static void main(String[] args){
        int[] array = {0,0,1,4,0,2,0,2,0,1,0,0,0,3,12};
        moveZeroes2(array);
        System.out.println(Arrays.toString(array));
        
        int[] array1 = {0,1,2,2,3,0,4,2};
        int len = removeElement(array1,2);
        System.out.println(Arrays.toString(Arrays.copyOfRange(array1,0,len)));
        
        int[] array2 = {0,1,2,2,3,0,4,2};
        Arrays.sort(array2);
        int len1 = removeDuplicates(array2);
        System.out.println(Arrays.toString(Arrays.copyOfRange(array2,0,len1)));
        
        int[] array3 = {0,0,1,1,1,1,2,2,2,2,2,2,3,3,4,4,4,4,4};
        int len2 = removeDuplicates2(array3);
        System.out.println(Arrays.toString(Arrays.copyOfRange(array3,0,len2)));
        
        int[] array4 = {0,0,1,1,1,1,2,2,2,2,2,2,3,3,4,4,4,4,4};
        int len3 = removeDuplicates3(array4);
        System.out.println(Arrays.toString(Arrays.copyOfRange(array4,0,len3)));
        
        int[] array5 = {2,0,2,1,1,0};
        sortColors(array5);
        System.out.println(Arrays.toString(array5));
        
        int[] numbers = {2,7,11,15};
        int target = 17;
        System.out.println(Arrays.toString(twoSum(numbers,target)));
        
        //    boolean status = isPalindrome("A man, a plan, a canal: Panama");
        boolean status = isPalindrome("0P");
        System.out.println(status);
        
        //    String str = reverseVowels("hello");
        String str = reverseVowels("a.");
        System.out.println(str);
        
        int[] height = {1,8,6,2,5,4,8,3,7};
        int max = maxArea(height);
        System.out.println(max);
        int[] array9 = {2,3,1,2,4,3};
        int length = minSubArrayLen(7,array9);
        System.out.println(length);
    }
    
    public static void moveZeroes1(int[] nums){
        int len = nums.length;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < len - 1; j++) {
                if (nums[j] == 0) {
                    nums[j] = nums[j] ^ nums[j + 1];
                    nums[j + 1] = nums[j] ^ nums[j + 1];
                    nums[j] = nums[j] ^ nums[j + 1];
                }
            }
        }
    }
    
    /**
     * 移动0
     *
     * @param nums 输入数组
     */
    public static void moveZeroes2(int[] nums){
        int len = nums.length;
        int i = -1;
        int j = 0;
        for (; j < len; j++) {
            if (nums[j] != 0) {
                i++;
                nums[i] = nums[j];
            }
        }
        for (; i < len; i++) {
            nums[i] = 0;
        }
    }
    
    /**
     * 删除指定的数据
     *
     * @param nums 输入数组
     * @param val 指定的数据
     * @return 新数组
     */
    public static int removeElement(int[] nums,int val){
        int len = nums.length;
        int index = 0;
        for (int j = 0; j < len; j++) {
            if (nums[j] != val) {
                nums[index] = nums[j];
                ++index;
            }
        }
        return index;
    }
    
    /**
     * 删除重复的数据
     *
     * @param nums 输入数组
     * @return 新数组长度
     */
    public static int removeDuplicates(int[] nums){
        int slow = 0;
        int fast = 1;
        while (fast <= nums.length - 1) {
            if (nums[slow] != nums[fast]) {
                nums[slow + 1] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow + 1;
    }
    
    /**
     * 删除重复的数据
     *
     * @param nums 输入数组
     * @return 新数组长度
     */
    public static int removeDuplicates2(int[] nums){
        int slow = 0;
        int fast = 1;
        while (fast <= nums.length - 1) {
            if (nums[slow] != nums[fast]) {
                if (fast - slow >= 2) {
                    nums[slow + 2] = nums[fast];
                }
                slow++;
            }
            fast++;
        }
        return slow + 2;
    }
    
    /**
     * 滑动窗口求解删除保留固定长度的数组
     *
     * @param nums 输入数组
     * @return 保留的数组的长度
     */
    public static int removeDuplicates3(int[] nums){
        int len = nums.length;
        int i = 1;
        int k = i - 1;
        int j = i + 1;
        for (; j < len; j++) {
            boolean status1 = nums[i] != nums[j];
            boolean status2 = nums[i] == nums[j] && nums[j] != nums[k];
            if (status1 || status2) {
                k = i;
                ++i;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
    
    /**
     * 颜色排序
     *
     * @param nums 输入数组排序
     */
    public static void sortColors(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length - i; j++) {
                if (nums[j - 1] > nums[j]) {
                    nums[j] = nums[j] ^ nums[j - 1];
                    nums[j - 1] = nums[j] ^ nums[j - 1];
                    nums[j] = nums[j] ^ nums[j - 1];
                }
            }
        }
    }
    
    /**
     * 定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
     *
     * @param numbers 输入数组
     * @param target 目标值
     * @return 结果数组
     */
    private static int[] twoSum(int[] numbers,int target){
        int slow = 0;
        int fast = 1;
        int len = numbers.length;
        int[] result = new int[2];
        while (fast < len) {
            if (numbers[slow] + numbers[fast] == target) {
                result[0] = slow + 1;
                result[1] = fast + 1;
                break;
            }
            slow++;
            if (slow == fast) {
                slow = 0;
                fast++;
            }
        }
        
        return result;
    }
    
    /**
     * 对撞指针实现判断回文串
     *
     * @param s 输入字符串
     * @return 判断逻辑
     */
    public static boolean isPalindrome(String s){
        String str = s.replaceAll("[^a-zA-Z0-9]","").toLowerCase(Locale.ENGLISH);
        int left = 0;
        int right = str.length() - 1;
        boolean status = true;
        while (left <= right) {
            if (str.charAt(left) != str.charAt(right)) {
                status = false;
                break;
            }
            left++;
            right--;
        }
        return status;
    }
    
    /**
     * 反转字符串中的元音字母
     *
     * @param s 输入字符串
     * @return 操作之后的字符串
     */
    public static String reverseVowels(String s){
        int left = 0;
        int right = s.length() - 1;
        String str = "aeiouAEIOU";
        while (left < right) {
            if (!str.contains(s.charAt(right) + "")) {
                right--;
                continue;
            }
            if (!str.contains(s.charAt(left) + "")) {
                left++;
                continue;
            }
            s = s.substring(0,left) + s.charAt(right) + s.substring(left + 1,right) + s.charAt(left) + s.substring(right + 1);
            left++;
            right--;
        }
        return s;
    }
    
    public static int maxArea(int[] height){
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        int resultArea = 0;
        while (left < right) {
            area = (right - left) * Math.min(height[left],height[right]);
            if (resultArea < area) {
                resultArea = area;
            }
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return resultArea;
    }
    
    public static int minSubArrayLen(int s,int[] nums){
        int left = 0;
        int right = left + 1;
        int len = nums.length;
        int max = 0;
        while (right < len) {
            if (left == right) {
                left = 0;
                right++;
            }
            if (nums[left] + nums[right] >= s) {
                int length = right - left + 1;
                if (length > max) {
                    max = length;
                }
            }
            left++;
        }
        return max;
    }
}
